package com.wtx.chapter13;

/**
 * @description: 红黑树, Red Black Tree
 * @author: wtx
 * @createDate: 2020/6/2
 */
public class RBTree <K extends Comparable<K>,V>{

    private Node root;
    private Integer size;

    public void add(K key,V value){
        root = add(root,key,value);
        root.isRed = false;     //根节点保持为黑色
    }

    //返回插入节点的新红黑树的根节点
    private Node add(Node node, K key, V value) {
        if (node == null){
            size++;
            return new Node(key,value);
        }
        if (key.compareTo(node.key)<0)  //key< node.key
            node.left = add(node.left,key,value);
        else if (key.compareTo(node.key)>0) //key>node.key
            node.right = add(node.right,key,value);
        else    //key == node.key
            node.value = value;

        //维护红黑树

        //是否需要左转
        if (node.right.isRed && !node.left.isRed)
            node = leftRotate(node);
        //是否需要右转
        if (node.left.isRed && node.left.left.isRed)
            node = rightRotate(node);
        //是否需要颜色反转
        if (node.left.isRed && node.right.isRed)
            filpColor(node);

        return node;
    }

    //   node                     x
    //  /   \     左旋转         /  \
    // T1   x   --------->   node   T3
    //     / \              /   \
    //    T2 T3            T1   T2
    private Node leftRotate(Node node){
        Node x = node.right;

        //左转
        node.right = x.left;
        x.left = node;

        //颜色调整: 注意, 左转并不一定会保持红黑树的性质,
        //这需要在添加操作的后续步骤继续调整
        x.isRed = node.isRed;
        node.isRed = true;
        return x;
    }

    //     node                   x
    //    /   \     右旋转       /  \
    //   x    T2   ------->   y   node
    //  / \                       /  \
    // y  T1                     T1  T2
    private Node rightRotate(Node node){

        Node x = node.left;

        //右转
        node.left = x.right;
        x.right = node;

        //颜色调整
        x.isRed = node.isRed;
        node.isRed = true;

        return x;
    }

    //颜色翻转
    private void filpColor(Node node){
        node.isRed = true;  //变为红色是为了继续和父节点融合
        node.left.isRed = false;
        node.right.isRed = false;
    }

    public RBTree() {
        this.root = null;
        this.size = 0;
    }

    private class Node{
        public K key;
        public V value;
        public Node left,right;
        public boolean isRed;   //是否为红色

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            //为什么默认为红色? -> 红黑树和2-3树等价, 而2-3树添加元素时
            // 必定会与某个元素融合, 所以可以先定为红色
            this.isRed = true;
            this.left = null;
            this.right = null;
        }
    }
}
